"""
难度：中等
给定一个由整数数组 A 表示的环形数组 C，求 C 的非空子数组的最大可能和。
在此处，环形数组意味着数组的末端将会与开头相连呈环状。（形式上，当0 <= i < A.length 时 C[i] = A[i]，且当 i >= 0 时 C[i+A.length] = C[i]）
此外，子数组最多只能包含固定缓冲区 A 中的每个元素一次。（形式上，对于子数组 C[i], C[i+1], ..., C[j]，不存在 i <= k1, k2 <= j 其中 k1 % A.length = k2 % A.length）
示例 1：
输入：[1,-2,3,-2]
输出：3
解释：从子数组 [3] 得到最大和 3
示例 2：
输入：[5,-3,5]
输出：10
解释：从子数组 [5,5] 得到最大和 5 + 5 = 10
示例 3：
输入：[3,-1,2,-1]
输出：4
解释：从子数组 [2,-1,3] 得到最大和 2 + (-1) + 3 = 4
示例 4：
输入：[3,-2,2,-3]
输出：3
解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3
示例 5：
输入：[-2,-3,-1]
输出：-1
解释：从子数组 [-1] 得到最大和 -1
"""
"""
解题思路：
构成环形整数数组 nums 的非空子数组的最大和的子数组有两种情况：
最大和的子数组为一个子区间：。
最大和的子数组为首尾的两个子区间：。
第一种情况其实就是无环情况下的整数数组的非空子数组最大和问题，跟「 53. 最大子序和」问题是一致的，我们假设求解结果为 max_num。
下来来思考第二种情况，第二种情况下，要使首尾两个子区间的和尽可能的大，则中间的子区间的和应该尽可能的小。
使得中间子区间的和尽可能小的问题，可以转变为求解：整数数组 nums 的非空子数组最小和问题。求解思路跟上边是相似的，只不过最大变为了最小。我们假设求解结果为 min_num。
而首尾两个区间和尽可能大的结果为数组 nums 的和减去中间最小子数组和，即 sum(nums) - min_num。
最终的结果就是比较 sum(nums) - min_num 和 max_num的大小，返回较大值即可。
"""

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        size = len(nums)

        dp_max, dp_min = nums[0], nums[0]
        max_num, min_num = nums[0], nums[0]
        for i in range(1, size):
            dp_max = max(dp_max + nums[i], nums[i])
            dp_min = min(dp_min + nums[i], nums[i])
            max_num = max(dp_max, max_num)
            min_num = min(dp_min, min_num)
        sum_num = sum(nums)
        if max_num < 0:
            return max_num
            
        return max(sum_num - min_num, max_num)